use std::{cell::RefCell, fmt, rc::Rc};

#[derive(Clone, Copy, PartialEq)]
pub enum RbColor {
    Red,
    Black,
    Blue,
}

impl fmt::Display for RbColor {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        match self {
            &RbColor::Black => write!(f, "Black"),
            &RbColor::Blue => write!(f, "Blue"),
            &RbColor::Red => write!(f, "Red"),
        }
    }
}

#[derive(Clone)]
pub struct RbNode<T: PartialEq + Copy + fmt::Display> {
    p: Option<RefCell<Rc<RbNode<T>>>>,
    key: RefCell<T>,
    left: Option<RefCell<Rc<RbNode<T>>>>,
    right: Option<RefCell<Rc<RbNode<T>>>>,
    color: RefCell<RbColor>,
}

impl<T: PartialEq + Copy + fmt::Display> fmt::Display for RbNode<T> {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        write!(f, "{}({})", self.get_key(), self.get_color())
    }
}

impl<T: PartialEq + Copy + fmt::Display> RbNode<T> {
    pub fn left_v(&self) -> T {
        self.get_left_node().get_key()
    }
    pub fn left_color(&self) -> RbColor {
        self.get_left_node().get_color()
    }
    pub fn right_v(&self) -> T {
        self.get_right_node().get_key()
    }
    pub fn right_color(&self) -> RbColor {
        self.get_right_node().get_color()
    }
    pub fn p_v(&self) -> T {
        self.get_p_node().get_key()
    }
    pub fn p_color(&self) -> RbColor {
        self.get_p_node().get_color()
    }

    pub fn get_color(&self) -> RbColor {
        unsafe { *(self.color.as_ptr()).clone() }
    }
    pub fn get_key(&self) -> T {
        unsafe { *(self.key.as_ptr()).clone() }
    }

    pub fn set_p(&self, p: Rc<RbNode<T>>) {
        if let Some(old_p) = self.p.as_ref() {
            *old_p.borrow_mut() = p;
        }
    }
    pub fn set_l(&self, l: Rc<RbNode<T>>) {
        if let Some(old_l) = self.left.as_ref() {
            *old_l.borrow_mut() = l;
        }
    }
    pub fn set_r(&self, r: Rc<RbNode<T>>) {
        if let Some(old_r) = self.right.as_ref() {
            *old_r.borrow_mut() = r;
        }
    }

    pub fn get_left_node(&self) -> Rc<RbNode<T>> {
        unsafe {
            if let Some(left) = self.left.as_ref() {
                Rc::clone(&(*left.as_ptr()))
            } else {
                Rc::new(self.clone())
            }
        }
    }
    pub fn get_right_node(&self) -> Rc<RbNode<T>> {
        unsafe {
            if let Some(right) = self.right.as_ref() {
                Rc::clone(&(*right.as_ptr()))
            } else {
                Rc::new(self.clone())
            }
        }
    }
    pub fn get_p_node(&self) -> Rc<RbNode<T>> {
        unsafe {
            if let Some(p) = self.p.as_ref() {
                Rc::clone(&(*p.as_ptr()))
            } else {
                Rc::new(self.clone())
            }
        }
    }
}

impl<T: PartialEq + Copy + fmt::Display> RbNode<T> {
    pub fn build(k: T) -> Self {
        RbNode {
            p: None,
            key: RefCell::new(k),
            left: None,
            right: None,
            color: RefCell::new(RbColor::Blue),
        }
    }
    pub fn build_nil(k: T, nil: Option<RefCell<Rc<RbNode<T>>>>) -> Self {
        RbNode {
            p: nil.clone(),
            key: RefCell::new(k),
            left: nil.clone(),
            right: nil,
            color: RefCell::new(RbColor::Red),
        }
    }
    pub fn set_color(&self, c: RbColor) {
        *(self.color.borrow_mut()) = c;
    }
}

pub struct RbTree<T: PartialEq + Copy + fmt::Display> {
    root: RefCell<Rc<RbNode<T>>>,
}
impl<T: PartialEq + Copy + fmt::Display> fmt::Display for RbTree<T> {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        let root = unsafe { Rc::clone(&(*self.root.as_ptr())) };
        if root.get_color() != RbColor::Blue {
            let mut node_list: Vec<Rc<RbNode<T>>> = Vec::new();
            let mut node_list_temp: Vec<Rc<RbNode<T>>> = Vec::new();
            node_list.push(Rc::clone(&root));
            while !node_list.is_empty() {
                node_list_temp.clear();
                for node in node_list.iter() {
                    if node.get_color() != RbColor::Blue {
                        print!("{} --- ", node);
                        node_list_temp.push(node.get_left_node());
                        node_list_temp.push(node.get_right_node());
                    } else {
                        print!("Nul --- ");
                    }
                }
                println!("|");
                node_list = node_list_temp.clone();
            }
            write!(f, "Over")
        } else {
            write!(f, "Empty!")
        }
    }
}

impl<T: PartialEq + Copy + fmt::Display + PartialOrd + Default> RbTree<T> {
    pub fn build(nil: Rc<RbNode<T>>) -> Self {
        RbTree {
            root: RefCell::new(nil),
        }
    }
    pub fn get_root(&self) -> Rc<RbNode<T>> {
        unsafe { Rc::clone(&(*self.root.as_ptr())) }
    }
    pub fn change(&self, v: Rc<RbNode<T>>) {
        *(self.root.borrow_mut()) = Rc::clone(&v);
    }
    pub fn rb_minimum(&self, x: Rc<RbNode<T>>) -> Rc<RbNode<T>> {
        let mut node = Rc::clone(&x);
        let mut node_p = Rc::clone(&x);
        while node.get_color() != RbColor::Blue {
            node_p = Rc::clone(&node);
            node = node.get_left_node();
        }
        node_p
    }
    pub fn rb_successor(&self, x: Rc<RbNode<T>>) -> Rc<RbNode<T>> {
        if x.get_right_node().get_color() != RbColor::Blue {
            return self.rb_minimum(Rc::clone(&x.get_right_node()));
        }
        let mut y = x.get_p_node();
        let mut x = x;
        while y.get_color() != RbColor::Blue && x.get_key() == y.get_right_node().get_key() {
            x = Rc::clone(&y);
            y = Rc::clone(&y.get_p_node());
        }
        Rc::clone(&y)
    }
    pub fn left_rotate(&self, x: Rc<RbNode<T>>) {
        let y = x.get_right_node();
        let y_left = y.get_left_node();
        x.set_r(Rc::clone(&y_left));
        if y_left.get_color() != RbColor::Blue {
            y_left.set_p(Rc::clone(&x));
        }
        let x_p = x.get_p_node();
        y.set_p(Rc::clone(&x_p));
        if x_p.get_color() == RbColor::Blue {
            self.change(Rc::clone(&y));
        } else if x.get_key() == x_p.left_v() {
            x_p.set_l(Rc::clone(&y));
        } else {
            x_p.set_r(Rc::clone(&y));
        }
        y.set_l(Rc::clone(&x));
        x.set_p(Rc::clone(&y));
    }
    pub fn right_rotate(&mut self, y: Rc<RbNode<T>>) {
        let x = y.get_left_node();
        let x_right = x.get_right_node();
        y.set_l(Rc::clone(&x_right));
        if x_right.get_color() != RbColor::Blue {
            x_right.set_p(Rc::clone(&y));
        }
        let y_p = y.get_p_node();
        x.set_p(Rc::clone(&y_p));
        if y_p.get_color() == RbColor::Blue {
            self.change(Rc::clone(&x));
        } else if y.get_key() == y_p.right_v() {
            y_p.set_r(Rc::clone(&x));
        } else {
            y_p.set_l(Rc::clone(&x));
        }
        x.set_r(Rc::clone(&y));
        y.set_p(Rc::clone(&x));
    }
    pub fn insert(&mut self, z: RbNode<T>) {
        println!("------------------------");
        println!("插入值：{}({})", z.get_key(), z.get_color());
        let mut y = Rc::new(z);
        let z = Rc::clone(&y);
        let z_key = z.get_key();
        let mut x = self.get_root();
        if x.get_color() != RbColor::Blue {
            while x.get_color() != RbColor::Blue {
                y = Rc::clone(&x);
                if z_key < x.get_key() {
                    x = Rc::clone(&x.get_left_node());
                } else {
                    x = Rc::clone(&x.get_right_node());
                }
                print!("{}({})-->", y.get_key(), y.get_color());
            }
            println!("{}({})", z_key, z.get_color());
            z.set_p(Rc::clone(&y));
            if z_key < y.get_key() {
                y.set_l(Rc::clone(&z));
            } else {
                y.set_r(Rc::clone(&z));
            }
        } else {
            self.change(Rc::clone(&z));
        }
        self.rb_insert_fixup(Rc::clone(&z));
        println!("------------------------");
        println!("{}", self);
    }
    pub fn rb_insert_fixup(&mut self, z: Rc<RbNode<T>>) {
        let mut z = Rc::clone(&z);
        while z.get_p_node().get_color() == RbColor::Red {
            let z_p = z.get_p_node();
            let z_p_p = z_p.get_p_node();
            println!("z_p: {}-{}", z_p.get_key(), z_p.get_color());
            println!("z_p_p: {}-{}", z_p_p.get_key(), z_p_p.get_color());
            if z_p_p.get_color() == RbColor::Blue {
                break;
            }
            if z_p.get_key() == z_p_p.left_v() {
                let y = z_p_p.get_right_node();
                if y.get_color() == RbColor::Red {
                    println!("Sample 1");
                    z_p.set_color(RbColor::Black);
                    y.set_color(RbColor::Black);
                    z_p_p.set_color(RbColor::Red);
                    z = Rc::clone(&z_p_p);
                } else if z.get_key() == z.get_p_node().right_v() {
                    println!("Sample 2");
                    z = Rc::clone(&z.get_p_node());
                    self.left_rotate(Rc::clone(&z));
                } else {
                    println!("Sample 3");
                    z.get_p_node().set_color(RbColor::Black);
                    z.get_p_node().get_p_node().set_color(RbColor::Red);
                    self.right_rotate(Rc::clone(&z.get_p_node().get_p_node()));
                }
            } else {
                let y = z_p_p.get_left_node();
                if y.get_color() == RbColor::Red {
                    println!("Sample 1");
                    z_p.set_color(RbColor::Black);
                    y.set_color(RbColor::Black);
                    z_p_p.set_color(RbColor::Red);
                    z = Rc::clone(&z_p_p);
                } else if z.get_key() == z.get_p_node().left_v() {
                    println!("Sample 2");
                    z = Rc::clone(&z.get_p_node());
                    self.right_rotate(Rc::clone(&z));
                } else {
                    println!("Sample 3");
                    z.get_p_node().set_color(RbColor::Black);
                    z.get_p_node().get_p_node().set_color(RbColor::Red);
                    self.left_rotate(Rc::clone(&z.get_p_node().get_p_node()));
                }
            }
        }
        self.get_root().set_color(RbColor::Black);
    }
    fn rb_transplant(&mut self, u: Rc<RbNode<T>>, v: Rc<RbNode<T>>) {
        let u_p = u.get_p_node();
        if u_p.get_color() == RbColor::Blue {
            self.change(Rc::clone(&v));
        } else {
            if u_p.left_v() == u.get_key() {
                u_p.set_l(Rc::clone(&v));
            } else {
                u_p.set_r(Rc::clone(&v));
            }
        }
        v.set_p(Rc::clone(&u_p));
    }
    pub fn rb_delete(&mut self, z: Rc<RbNode<T>>) {
        println!("------------------------");
        println!("删除节点：{}({})", z.get_key(), z.get_color());
        let mut y_original_color = z.get_color();
        let mut x = Rc::clone(&z);
        let z = Rc::clone(&x);
        if z.left_color() == RbColor::Blue {
            x = z.get_right_node();
            self.rb_transplant(Rc::clone(&z), Rc::clone(&x));
        } else if z.right_color() == RbColor::Blue {
            x = z.get_left_node();
            self.rb_transplant(Rc::clone(&z), Rc::clone(&x));
        } else {
            let y = self.rb_minimum(z.get_right_node());
            y_original_color = y.get_color();
            x = y.get_right_node();
            println!("被删除节点的后继： {}({})", y.get_key(), y.get_color());
            if y.p_v() != z.get_key() {
                self.rb_transplant(Rc::clone(&y), Rc::clone(&x));
                let z_right = z.get_right_node();
                y.set_r(Rc::clone(&z_right));
                z_right.set_p(Rc::clone(&y));
            }
            self.rb_transplant(Rc::clone(&z), Rc::clone(&y));
            let z_left = z.get_left_node();
            y.set_l(Rc::clone(&z_left));
            z_left.set_p(Rc::clone(&y));
            y.set_color(z.get_color());
        }
        println!("删除完成，开始修正");
        if y_original_color == RbColor::Black && x.get_color() != RbColor::Blue {
            self.rb_delete_fixup(Rc::clone(&x));
        }
    }
    fn rb_delete_fixup(&mut self, x: Rc<RbNode<T>>) {
        let mut x = x;
        let root_key = self.get_root().get_key();
        while x.get_key() != root_key && x.get_color() == RbColor::Black {
            let x_p = x.get_p_node();
            if x.get_key() == x_p.get_left_node().get_key() {
                let mut w = x_p.get_right_node();
                if w.get_color() == RbColor::Red {
                    w.set_color(RbColor::Black);
                    x_p.set_color(RbColor::Red);
                    self.left_rotate(Rc::clone(&x_p));
                    w = x_p.get_right_node();
                }
                let w_left = w.get_left_node();
                let w_right = w.get_right_node();
                if w_left.get_color() == RbColor::Black && w_right.get_color() == RbColor::Black {
                    w.set_color(RbColor::Red);
                    x = x.get_p_node();
                } else if w_right.get_color() == RbColor::Black {
                    w_left.set_color(RbColor::Black);
                    w.set_color(RbColor::Red);
                    self.right_rotate(Rc::clone(&w));
                    w = x_p.get_right_node();
                }
                w.set_color(x_p.get_color());
                x.get_p_node().set_color(RbColor::Black);
                w.get_right_node().set_color(RbColor::Black);
                self.left_rotate(Rc::clone(&x_p));
                x = self.get_root();
            } else {
                let mut w = x_p.get_left_node();
                if w.get_color() == RbColor::Red {
                    w.set_color(RbColor::Black);
                    x_p.set_color(RbColor::Red);
                    self.right_rotate(Rc::clone(&x_p));
                    w = x_p.get_left_node();
                }
                let w_right = w.get_right_node();
                let w_left = w.get_left_node();
                if w_right.get_color() == RbColor::Black && w_left.get_color() == RbColor::Black {
                    w.set_color(RbColor::Red);
                    x = x.get_p_node();
                } else if w_left.get_color() == RbColor::Black {
                    w_right.set_color(RbColor::Black);
                    w.set_color(RbColor::Red);
                    self.left_rotate(Rc::clone(&w));
                    w = x_p.get_left_node();
                }
                w.set_color(x_p.get_color());
                x.get_p_node().set_color(RbColor::Black);
                w.get_left_node().set_color(RbColor::Black);
                self.right_rotate(Rc::clone(&x_p));
                x = self.get_root()
            }
        }
        x.set_color(RbColor::Black);
    }
    pub fn rb_find(&self, v: T) -> Rc<RbNode<T>> {
        let mut root = self.get_root();
        while root.get_key() != v {
            if v > root.get_key() {
                root = root.get_right_node();
            } else {
                root = root.get_left_node();
            }
        }
        Rc::clone(&root)
    }
}

/*
   let nil = Rc::new(RbNode::build(5));
   let nil_option = Some(RefCell::new(Rc::clone(&nil)));
   let mut b = RbTree::<i32>::build(Rc::clone(&nil));

   b.insert(RbNode::build_nil(26, nil_option.clone()));
   b.insert(RbNode::build_nil(17, nil_option.clone()));
   b.insert(RbNode::build_nil(41, nil_option.clone()));
   b.insert(RbNode::build_nil(14, nil_option.clone()));
   b.insert(RbNode::build_nil(30, nil_option.clone()));
   b.insert(RbNode::build_nil(21, nil_option.clone()));
   b.insert(RbNode::build_nil(47, nil_option.clone()));
   b.insert(RbNode::build_nil(10, nil_option.clone()));
   b.insert(RbNode::build_nil(16, nil_option.clone()));
   b.insert(RbNode::build_nil(19, nil_option.clone()));
   b.insert(RbNode::build_nil(23, nil_option.clone()));
   b.insert(RbNode::build_nil(28, nil_option.clone()));
   b.insert(RbNode::build_nil(38, nil_option.clone()));
   b.insert(RbNode::build_nil(7, nil_option.clone()));
   b.insert(RbNode::build_nil(12, nil_option.clone()));
   b.insert(RbNode::build_nil(15, nil_option.clone()));
   b.insert(RbNode::build_nil(20, nil_option.clone()));
   b.insert(RbNode::build_nil(35, nil_option.clone()));
   b.insert(RbNode::build_nil(39, nil_option.clone()));
   b.insert(RbNode::build_nil(3, nil_option.clone()));
   b.rb_delete(b.rb_find(17));
   println!("{}", b);
*/
